package com.itheima.leetcode.od.c.backtracking;

import java.util.*;

/**
 * <h3>分批萨</h3>
 */
public class BatchSa {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取披萨数量
        int n = scanner.nextInt();
        // 存储每块披萨的大小
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 初始化记忆化数组
        memory = new long[n][n];

        // 计算最终结果
        long result = 0;
        // 尝试从每个位置开始选择
        for (int i = 0; i < n; i++) {
            // 计算当前位置的左右相邻位置
            int left = (i - 1 + n) % n;  // 环形数组左边界
            int right = (i + 1) % n;     // 环形数组右边界
            // 计算从当前位置开始能获得的最大值
            long target = recursive(left, right, nums, n);
            // 更新全局最大值
            result = Math.max(result, target + nums[i]);
        }

        // 输出结果
        System.out.print(result);
        scanner.close();
    }

    // 全局记忆化数组，用于存储已计算过的状态
    // memory[left][right]表示从left到right区间能获得的最大值
    static long[][] memory;

    public static long recursive(int left, int right, int[] nums, int n) {
        // 根据大小关系调整指针
        // 由于馋嘴总是选最大的，我们可以根据大小关系确定他的选择
        if (nums[left] > nums[right]) {
            // 如果左边更大，馋嘴会选左边
            left = (left - 1 + n) % n;  // 环形数组，向左移动
        } else {
            // 如果右边更大或相等，馋嘴会选右边
            right = (right + 1) % n;  // 环形数组，向右移动
        }

        // 如果该位置未计算过
        if (memory[left][right] <= 0) {
            if (left == right) {
                // 如果只剩一块，直接返回这块的大小
                memory[left][right] = nums[left];
            } else {
                // 计算新的左右边界
                int newLeft = (left - 1 + n) % n;
                int newRight = (right + 1) % n;
                // 递归计算两种选择的结果，取最大值
                // 1. 选择左边的披萨
                // 2. 选择右边的披萨
                memory[left][right] = Math.max(
                        nums[left] + recursive(newLeft, right, nums, n),
                        nums[right] + recursive(left, newRight, nums, n)
                );
            }
            return memory[left][right];
        } else {
            // 如果已经计算过，直接返回记忆化的结果
            return memory[left][right];
        }
    }
}